<<<<<<< HEAD ======= >>>>>>> 38470dc1b04fa68e4367c4aa05a819260380c722 7-Machine learning

7-Machine learning

Thibaut Goetsch

GMRC

Programme

  • Aujourd’hui : Algorithmes + tuto R
  • 15 février tuto python

Rappel

Stratégie d’apprentissage pour le choix du modèle et des hyperparamètres.

Algorithmes de machine learning

KNN

  • Used for Classification

  • Need standardized variable

  • One of the easiest algorithm

Linear Regression

  • Used for predicting a continuous value

  • Formulas:

  • \(y = mx + b\) (where \(y\) is the predicted value, \(x\) is the input feature, \(m\) is the slope, and \(b\) is the y-intercept)

  • Mean Squared Error (MSE) loss function: \(\frac{1}{n}\sum_{i=1}^n(y_i - \hat{y_i})^2\)

Logistic Regression

  • Used for predicting a binary outcome (e.g. yes/no, pass/fail)

  • Formulas:

  • sigmoid function: $ $ (where \(z\) is the input to the function)

Regression with regulation

  • reduces complexity of regression

  • allow the use of correlated variables

Decision Tree

  • Used for both classification and regression

  • good for interaction

  • Understable

Random Forest

  • Used for both classification and regression

  • Bootstrap Aggregating (Bagging)

  • Random Subspace Method (RSM)

Support Vector Machine (SVM)

  • Used for classification

  • Formulas:

  • Linear SVM : \(y = wx + b\)

  • Non-Linear SVM : \(y = \sum_{i=1}^{n} \alpha_i y_i K(x_i,x) + b\)

Neural Network

  • Used for both classification and regression, as well as unsupervised learning

  • Feedforward: \(a = f(Wx + b)\)

  • Backpropagation: \(\frac{\partial L}{\partial w} = \frac{\partial L}{\partial a} * \frac{\partial a}{\partial w}\)

K-means Clustering

  • Used for unsupervised learning

  • Distance: \(d(x,y) = \sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}\)

  • Centroid: \(\mu_j = \frac{\sum_{i=1}^{n} 1_{c_i = j} x_i}{\sum_{i=1}^{n} 1_{c_i = j}}\)

Principal Component Analysis (PCA)

  • Used for unsupervised learning

  • Example: dimensionality reduction

XGBoost

  • XGBoost stands for “eXtreme Gradient Boosting”

  • It is an ensemble learning method for classification and regression problems

  • XGBoost is based on decision trees

  • XGBoost algorithm can handle missing values and can be used for feature selection

KNN

  • Algorithme des K plus proches voisins

Hyperparamètres des KNN :

  • Type de distance

  • Nombre de voisins

Arbre de décision

Exemple visuel

Arbre de décision

https://mlu-explain.github.io/decision-tree/

  • algorithme d’apprentissage supervisé

  • tâches de classification et de régression

  • nœud interne de l’arbre représente une caractéristique ou une propriété,

  • chaque nœud feuille représente une étiquette de classe ou une valeur

  • construction en divisant récursivement en fonction de la caractéristique qui donne les sous-ensembles les plus pures

Constructions Arbre de décision

  • en partant de la racine, qui représente l’ensemble des données d’entraînement

  • on choisit la caractéristique qui divise le mieux les données en sous-ensembles purs selon le critère choisi

  • jusqu’à ce qu’un certain critère d’arrêt soit atteint : profondeur max, nombre minimum de données par noeud

  • feuilles représentent les classes cibles

  • Arbre utiliser pour classifier de nouvelles données

Critère de séparation des données:

  • L’impureté de Gini : \[ Gini = 1 - \sum_{i=1}^{n}P(i|t)^2 \]

  • \(P(i|t)\) : la probabilité d’appartenance à la classe \(i\) pour les données dans le nœud \(t\).

L’impureté de Gini : probabilité qu’un élément choisit au hasard dans le nœud soit mal classée.

Critère de séparation des données:

  • L’entropie :

\[ H(S) = -\sum_{i=1}^{n}P(i|S)log(P(i|S)) \]

  • \(P(i|S)\) : la probabilité d’appartenance à la classe \(i\) pour les données dans l’ensemble \(S\). L’entropie : incertitude des données dans l’ensemble.

Exemple arbre de décision

couleur poids (kg) nombre de pépins type
rouge 0.5 5 fraise
rouge 0.8 10 framboise
jaune 0.3 2 cerise
vert 0.7 8 pomme
vert 0.6 3 poire

Exemple arbre de décision

couleur poids (kg) nombre de pépins type
rouge 0.5 5 fraise
rouge 0.8 10 framboise
jaune 0.3 2 cerise
vert 0.7 8 pomme
vert 0.6 3 poire
  1. On calcule l’entropie pour chaque propriété pour chaque propriété (couleur, poids, nombre de pépins) en utilisant les données de l’ensemble.
couleur poids (kg) nombre de pépins type
rouge 0.5 5 fraise
rouge 0.8 10 framboise
jaune 0.3 2 cerise
vert 0.7 8 pomme
vert 0.6 3 poire

\[ Gini(base) = 1-1/5^2-1/5^2-1/5^2-1/5^2-1/5^2 \]

\[ Gini(couleur) = 1 - \sum_{i=1}^{n}P(i|couleur)^2 \]

\[ Gini(poids) = 1 - \sum_{i=1}^{n}P(i|poids)^2 \]

\[ Gini(nombre\ de\ pépins) = 1 - \sum_{i=1}^{n}P(i|nombre\ de\ pépins)^2 \]

Calcul pour couleur :

\[ Gini(rouge) = 1 - \sum_{i=1}^{n}P(i|rouge)^2 = 1 - 0^2 - 0^2-0.5^2-0.5^2 = 0.75 \]

\[ Gini(jaune) = 1 - \sum_{i=1}^{n}P(i|rouge)^2 =\\ 1 - 0^2 - 0^2-1^2-0^2 = 0 \] \[ Gini(vert) = 1 - \sum_{i=1}^{n}P(i|rouge)^2 = 1 - 0.5^2 - 0^2-0.5^2-0^2 = 0.75 \] \[ Impurete\_moyenne = 2/5*Gini(rouge)+1/5*Gini(ver)\\+2/5*Gini(jaune) = 0.6 \]

Calcul pour nombre de pépins :

  • \[ Gini(nbpepin>4) = 1 - \sum_{i=1}^{n}P(i|nbpepin>4)^2 =\\ 1 -0^2- 0^2 - 1/3^2-1/3^2-1/3^2 = 0.66 \]

  • \[ Gini(nbpep\leq4) = 1 - \sum_{i=1}^{n}P(i|\leq4)^2 = \\1 -1/2^2- 1/2^2 - 0^2-0^2-0^2 = 0.75 \]

  • \[Gini(nb\_pep) = 2/3*0.66+1/3*0.75 = 0.69 \]

  1. propriété qui minimise l’impureté de Gini pour séparation : \(nb_pep \leq4\).

  2. On crée deux sous-nœuds pour les fruits avec plus ou moins de 4 pépins

  3. On répète les étapes 1 à 3 pour chaque sous-nœud en utilisant uniquement les données associées à ce sous-nœud. Exemple, \[ Gini(poids | nbpep\leq4) = 1 - \sum_{i=1}^{n}P(i|poids,nbpep\leq4)^2 \]

  4. On répète jusqu’au critère de fin

Hyperparamètres arbre de decision

  • Criterion : entropy ou gini

  • splitter : best ou random

  • Profondeur maximale : \(Max\_depth\)

  • Nombre minimum d’éléments dans un noeud de feuille : \(Min\_samples\_leaf\)

  • Nombre maximum de feuilles : \(Max\_leaf\_nodes\)

  • Nombre minimum de split : \(Min\_samples\_split\)

Pruning arbre :

  • Pré-élagage : règle d’arrêt évaluer à chaque nouveau nœud qui stoppe la construction de l’arbre -> méthode de haut en bas

  • Post-élagage : Construction de l’arbre dans son intégralité puis calcul de l’intérêt de chaque nœud en partant des nœuds terminaux -> méthode de bas en haut

Avantages inconvénients :

  • Compréhensible par un humain

  • Pas besoin de normaliser les données

  • Accepte les données quanti et quali

  • Pb de surapprentissage

  • Pb avec les classifications non équilibrés

GIF

Interpretability and Random Forests | by Tom Grigg | Towards Data Science

Implémentation R et Python

  • r : rpart https://ouvrir.passages.cnrs.fr/arbre_decision/_book/pratique.html

  • python : sklearn.tree.DecisionTreeClassifier

Régression logistique

https://mlu-explain.github.io/logistic-regression/

  • Y binaire

  • Modélisation de \[ P(Y=1) \]

  • \(P(y=1|x) = \frac{1}{1 + e^{-(b_0 + b_1x_1 + b_2x_2 + ... + b_nx_n)}}\)

  • Fonction sigmoïdale comprise entre 0 et 1

Régression linéaire

  • Y quantitative

  • \(y = b_0 + b_1x_1 + b_2x_2 + ... + b_nx_n\)

  • possibilité d’effet non linéaire : \(y = b_0 + b_1x_1^2 + b_2x_2 + ... + b_nx_n\)

Regression pénalisée

  • Contraindre la valeur des estimateurs des moindres carrés pour réduire la variance

  • \(\beta = argmin_{\beta} { \sum_{i=1}^{n} (y_i - \beta_0 - \sum_{j=1}^{p}x_{ij}\beta_j)^2 + contrainte}\)

Ridge :

\(\beta = argmin_{\beta} { \sum_{i=1}^{n} (y_i - \beta_0 - \sum_{j=1}^{p}x_{ij}\beta_j)^2 + \lambda \sum_{j=1}^{p} \beta_j^2}\)

#\| output-location: column
library(glmnet)
y <- mtcars$hp
x <- mtcars %>% select(mpg, wt, drat) %>% data.matrix()
reg.ridge = glmnet(x, y, alpha=0)
par(mfrow = c(1, 2))
  plot(reg.ridge, lwd = 2)
  plot(reg.ridge, lwd = 2, xvar = "lambda")

CV de lambda

lambdas <- 10^seq(3, -2, by = -.1)
cv_fit <- cv.glmnet(x, y, alpha = 0, lambda = lambdas)
plot(cv_fit)
<<<<<<< HEAD
=======
>>>>>>> 38470dc1b04fa68e4367c4aa05a819260380c722

Regression LASSO

\(\beta = argmin_{\beta} { \sum_{i=1}^{n} (y_i - \beta_0 - \sum_{j=1}^{p}x_{ij}\beta_j)^2 + \lambda \sum_{j=1}^{p} |\beta_j|}\)

  • Lasso “defini à zéros les betas proches de 0”
reg.ridge = glmnet(x, y, alpha=1)
par(mfrow = c(1, 2))
  plot(reg.ridge, lwd = 2)
  plot(reg.ridge, lwd = 2, xvar = "lambda")

Elasticnet

Compromis ridge lasso

\(\beta = argmin_{\beta} { \sum_{i=1}^{n} (y_i - \beta_0 - \sum_{j=1}^{p}x_{ij}\beta_j)^2 + \lambda \sum_{j=1}^{p} ((1-\alpha)\beta_j^2 + \alpha|\beta_j|)}\)

  • si \(\alpha =0\) : ridge

  • si \(\alpha =0\) : lasso

Hyperparamètres régression pénalisée

  • alpha pour définir le type de pénalisation

  • lambda (force de la pénalisation)

Implémentation R et Python

  • r : glmnet

  • python : sklearn.linear_model <https://scikit-learn.org/stable/modules/linear_model.html

SVM (Machine à vecteur de support)

Règles linéaires :

  • Séparer l’espace \(X\) par un hyperplan

  • Classe positive : \(g(x) = \begin{cases} 1 & \text{si } w^Tx + b > 0 \\ -1 & \text{sinon} \end{cases}\)

  • définir le meilleur hyperplan par algorithme d’optimisation

Implémentation R et Python

  • r : e1071

  • python : sklearn.svm https://scikit-learn.org/stable/modules/svm.html

library(e1071)
x = matrix(rnorm(40), 20, 2)
y = rep(c(-1, 1), c(10, 10))
x[y == 1,] = x[y == 1,] + 1
plot(x, col = y + 3, pch = 19)
<<<<<<< HEAD
=======
>>>>>>> 38470dc1b04fa68e4367c4aa05a819260380c722
dat = data.frame(x, y = as.factor(y))
svmfit = svm(y ~ ., data = dat, kernel = "linear", cost = 10, scale = FALSE)
plot(svmfit, dat)
<<<<<<< HEAD
=======
>>>>>>> 38470dc1b04fa68e4367c4aa05a819260380c722

GIF

SVM : Cas non séparable

  • Rajout d’un paramètre de cout \(C\) à calibrer

SVM : Cas non séparable

  • \(C\) : constante de régularisation

  • \(C \searrow\) : augmentation de la marge, des erreurs

  • \(C \nearrow\) : diminution de la marge, risque surajustement

Séparation linéaire pas toujours possible

-

Fonction noyau

\[ K(\textbf{x}_i, \textbf{x}_j) = \phi(\textbf{x}_i)^T \phi(\textbf{x}_j) \]

  • SVM peuvent être appliqués sur \(\phi(x)\) sans calculer \(\phi\)

  • Il suffit de calculer le noyau \(K(x,x')\)

Type de noyau

  • Noyau linéaire:

    \[ K(\textbf{x}_i, \textbf{x}_j) = \textbf{x}_i^T \textbf{x}_j \]

  • Noyau polynomial: \[ K(\textbf{x}_i, \textbf{x}_j) = (\textbf{x}_i^T \textbf{x}_j + c)^d \]\(c\) est l’hyperparamètre de décalage et \(d\) est le degré du polynôme.

  • Noyau radial (ou gaussien): \[ K(\textbf{x}_i, \textbf{x}_j) = \exp\left(-\frac{|\textbf{x}_i - \textbf{x}_j|^2}{2\sigma^2}\right) \]\(\sigma\) est un des hyperparamètres appelé la largeur de bande.

  • Noyau sigmoid: \[ K(\textbf{x}_i, \textbf{x}_j) = \tanh(\alpha\textbf{x}_i^T \textbf{x}_j + r) \]\(\alpha\) et \(r\) sont des hyperparamètres.

Hyperparamètre

  • coût \(C\)
  • noyau
  • paramètres des noyaux

GIF

Bagging et forêts aléatoires

  • Bagging : vient de la contraction de Bootstrap Aggregating

  • Idée : plutôt que de construire un seul estimateur, en construire un grand nombre (sur des échantillons bootstrap) et les agréger.

  • Ajuster le même algo sur les mêmes données : sans intérêt

  • Ajuster le même algorithme sur des échantillons disjoints : peu généralisable

  • Ajuster bcp d’algorithmes différents : compliqué

Bootstrap

  • Échantillon initial : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

  • Bootstrap : tirages de n avec remise :

3 6 7 9 4 7 8 9 5 4 T1
3 6 7 9 4 7 8 9 5 4 T2
10 7 8 5 4 8 1 1 5 10 T3
. . . . . . . . . . .
6 8 4 10 9 8 1 7 9 2 TB

Forêt aléatoire

Forêt aléatoire

Rappel sur la profondeur des arbres :

  • petite : biais \(\searrow\), variance \(\nearrow\)

  • grande : biais \(\nearrow\), variance \(\searrow\)

  • Random forest : Nombreux petits arbres

Forêt aléatoire

  • Ensemble d’arbres

  • agrégations d’arbres constitués sur des échantillons bootstrapés

https://www.stat.berkeley.edu/~breiman/RandomForests/

Coupure aléatoire

  • Choix aléatoire des variables de chaque arbre

  • Idée : choisir la “meilleure” variable dans un ensemble réduit de variables

  • \(mtry\) nombre de variables choisies aléatoirement

  • but : diminuer la corrélation entre les arbres

Prévision:

\(\hat{y}(x) = \frac{1}{N}\sum_{i=1}^{N}[\hat{y}_{tree_i}(x)]\)

\(\hat{y}(x) = \text{argmax}_{c\in C} \sum_{i=1}^{N}[tree_i(x) = c]\)

Avantages Rf

  • Fonctionne bien avec des données de grande dimension

  • Effectue implicitement de la sélection de variables

  • Peu d’influence des outliers

  • Généralement efficace

  • Computationnellement lourd

  • Black box

Hyperparamètre :

  • n arbres

  • mtry, si trop grand -> surapprentissage

  • min.node.size : nombre minimum de noeuds par arbre / profondeur des arbres

R et Python

  • r : ranger ou randomforest
  • sklearn

OOB

Out of bag error : Estimation de l’erreur de classification sur les sujets non sélectionnés par le boosting

Boosting

• Le terme Boosting s’applique à des méthodes générales permettant de produire des décisions précises à partir de règles faibles (weaklearner)

Suite de petits algorithmes

Boosting

Kmean clustering

kmeans

Principes

  • Place the K centroids at random locations

  • Assign all data points to the closest centroid (using Euclidean distance)

  • Compute the new centroids as the mean of all points in the cluster

<<<<<<< HEAD

ACP

======= >>>>>>> 38470dc1b04fa68e4367c4aa05a819260380c722